The present invention relates to an encoding method for compressing a data structure having two or more dimensions, as in the case of image data, a decoding method for decoding the data that has been encoded, apparatus for executing these methods, and a computer-readable storage medium storing programs for executing these methods by computer.
An example of a method of compressing image data available in the art is one which uses run-length encoding. If the same data repeats itself, run-length encoding is used to encode the repeating lengths and data. By writing software efficiently, encoding can be performed at a fairly high speed.
Another example of an available method is one which uses delta row coding. If one line of data is followed directly by an identical line of data, delta low coding encodes the length of the succeeding line.
Yet another method which can be used is Huffman coding. This method of encoding investigates the distribution of data and encodes data having a high frequency of occurrence into short codes.
However, with the method that relies upon run-length encoding, even if there is correlation in both the horizontal and vertical directions, as in the case of image data, only correlation in the horizontal direction contributes to compression. If there is correlation only in the vertical direction, there is no contribution to compression. As a consequence, it is difficult to achieve a high compression rate overall with this method.
Delta row coding is capable of performing encoding at high speed by use of software. However, even if there is correlation in both the horizontal and vertical directions, as in the case of image data, only correlation in the vertical direction contributes to compression. If there is correlation only in the horizontal direction, there is no contribution to compression and it is difficult to achieve a high compression rate.
With Huffman coding, even if there is correlation in both the horizontal and vertical directions, as in the case of image data, correlation in neither direction contributes to compression and, hence, it is difficult to achieve a high compression rate.
Various other encoding methods such as LZ77, LZ78 and JBIG encoding have been proposed. With these methods, however, it is necessary to investigate data other than data immediately to the left and data immediately above, where the horizontal and vertical correlations are most conspicuous. As a result, encoding requires a large amount of calculation. In a case where encoding is performed by software, the encoding takes considerable time. In instances where decoding is performed by hardware, a decoder of large scale is required.
Further, in a conventional printing system, the printer driver program of a host computer creates bitmap data, which allows the printer to perform printing, based upon a print instruction issued from an application program, encodes (compresses) the bitmap data by an encoding procedure of the kind described above, and outputs the encoded bitmap data, together with control data necessary for printing control, to the printer as print data. The printer, which does not have enough memory for one page, controls printing on the basis of the control data in the print data received from the host computer, decodes (expands) the encoded bitmap data and prints the results on printing paper.
The conventional printing system, which generates bitmap data in the host computer and transmits the bitmap data to the printer, is such that the host computer and the printer are connected by a local interface. Transfer time needed to transfer data from the host computer to the printer is fixed. As a result, even though the printer memory does not have enough capacity for one page, and even though print processing is executed starting from print data received previously, reception of print data that follows this page can be processed in time for ejection of the printing paper. This makes it possible to prevent overrun error.
With modern networks, one printer can be shared by a plurality of host computers. Accordingly, in a case where PDL (Page Description Language) is generated in a host computer and is expanded and printed by the printer, overrun error will not occur regardless of how long transfer time is in the network. However, if bitmap data is generated in the host computer and bitmap print data (which does not contain PDL) is subjected to print processing by the printer, print processing is started before reception of one page of print data ends. If data transfer takes too much time, therefore, there is the possibility that overrun error will occur. For this reason, a printer which relies upon data expansion by the host computer is not used by being connected directly to the network.
Accordingly, it has been contemplated to encode bitmap data in order to hold data transfer time below a fixed value. However, print instructions issued from an application are of a variety of types, and the encoding rate (decompression rate) differs depending upon the type of document, as in a case where a document contains much text or a case where a document contains many images. If a code expression suited to text is used, therefore, almost no compression can be performed in case of a document containing many images, a great deal of time is required to transfer the print data and overrun error occurs. Similarly, encoding suited to an image is not appropriate for a document containing a large quantity of text.
Accordingly, consideration has been given to having a printer driver support a plurality of code expressions, analyze the print instruction issued from the application and select the suitable code expression. If this is done, however, a plurality of code expressions must be supported. This means high cost in case of support by hardware and slow processing and reduced throughput in case of support by software. Further, when a print instruction issued from an application is analyzed one time, throughput declines by an amount approximately equivalent to a code representation of two passes.
An object of the present invention, therefore, is to provide a single-pass code expression suited to the encoding of bitmap data created by a host computer in a printing system in which a host computer and a printer communicate via a network.
The present invention has been proposed to solve the problems of the prior art and an object thereof is to provide an encoding method and apparatus, a decoding method and apparatus and a storage medium therefor, wherein a high compression rate is obtained by utilizing correlations in both the horizontal and vertical directions to encode a data structure having two or more dimensions, as in the case of image data, and wherein the amount of computation can be reduced by investigating only data immediately to the left and data immediately above, where the horizontal and vertical correlations are most conspicuous, thereby shortening the required encoding time when encoding is performed by software.
Another object of the present invention is to raise encoding efficiency by encoding at least two of three types of operations used when correlations in both the horizontal and vertical directions are utilized, namely repeating, copying and raw-data substitution operations, simultaneously (i.e., by encoding a combination of any two of these).
According to the present invention, the foregoing objects are attained by providing a decoding method and apparatus, an encoding method and apparatus and a storage medium for executing these methods by computer, the characterizing features of which are as described below.
Specifically, a decoding method according to the present invention comprises the steps of: determining, based upon a received code sequence, to which of repetition, copying and raw-data the code sequence applies; decoding the code sequence, in accordance with the determination, by a combination of at least two conversion operations from among repetition, copying and raw-data substitution; performing address management for storing each item of decoded data at a prescribed address; and outputting results of decoding in a predetermined address order in accordance with the address management.
In accordance with a preferred embodiment of the decoding method, the repetition is repetition of an identical data byte.
In accordance with a preferred embodiment of the decoding method, the copying is copying of data of an immediately preceding line.
In accordance with a preferred embodiment of the decoding method, the raw data is a direct designation of a data sequence of a given command code.
In accordance with a preferred embodiment of the decoding method, the received code sequence is related to image data of two or more dimensions correlated in horizontal and vertical directions.
Further, an encoding method according to the present invention comprises the steps of: determining, based upon a bit sequence of a given command code, to which of repetition, copying and raw-data substitution the bit sequence applies; calculating data lengths of each of repetition, copying and raw data based upon the determination; and, in accordance with the calculations, combining and encoding as a command of one byte at least two of results from among results of repetition, copying and raw-data substitution of the encoding.
In accordance with a preferred embodiment of the encoding method, the repetition is repetition of an identical data byte.
In accordance with a preferred embodiment of the encoding method, the copying is copying of data of an immediately preceding line.
In accordance with a preferred embodiment of the encoding method, the raw data is a direct designation of a data sequence of the given command code.
In accordance with a preferred embodiment of the encoding method, the given command code is related to image data of two or more dimensions correlated in horizontal and vertical directions.
Further, there is provided a computer-readable storage medium storing a program for decoding encoded image data of two or more dimensions correlated in horizontal and vertical directions, wherein the program comprises: code of a step of determining, based upon a received code sequence, to which of repetition, copying and raw-data substitution the code sequence applies; code of a step of decoding the code sequence, in accordance with the determination, by a combination of at least two conversion operations from among repetition, copying and raw-data substitution; code of a step of performing address management for storing each item of decoded data at a prescribed address; and code of a step of outputting results of decoding in a predetermined address order in accordance with the address management.
Further, there is provided a computer-readable storage medium storing a program for encoding image data of two or more dimensions correlated in horizontal and vertical directions, wherein the program comprises: code of a step of determining, based upon a bit sequence of a given command code, to which of repetition, copying and raw-data substitution the bit sequence applies; code of a step of calculating data lengths of each of repetition, copying and raw data based upon the determination; and, in accordance with the calculations, code of a step of combining and encoding as a command of one byte at least two results from among results of repetition, copying and raw-data substitution of the encoding.
Further, a decoding apparatus according to the present invention comprises: means for determining, based upon a received code sequence, to which of repetition, copying and raw-data substitution the code sequence applies; means for decoding the code sequence, in accordance with the determination, by a combination of at least two conversion operations from among repetition, copying and raw-data substitution; means for performing address management for storing each item of decoded data at a prescribed address; and means for outputting results of decoding in a predetermined address order in accordance with the address management.
In accordance with a preferred embodiment of the decoding apparatus, the repetition is repetition of an identical data byte.
In accordance with a preferred embodiment of the decoding apparatus, the copying is copying of data of an immediately preceding line.
In accordance with a preferred embodiment of the decoding apparatus, the raw data is a direct designation of a data sequence of a given command code.
In accordance with a preferred embodiment of the decoding apparatus, the received code sequence is related to image data of two or more dimensions correlated in horizontal and vertical directions.
Further, an encoding apparatus according to the present invention comprises: means for determining, based upon a bit sequence of a given command code, to which of repetition, copying and raw-data substitution the bit sequence applies; means for calculating data lengths of each of repetition, copying and raw data based upon the determination; and, in accordance with the calculations, means for combining and encoding as a command of one byte at least two results from among results of repetition, copying and raw-data substitution of the encoding.
In accordance with a preferred embodiment of the encoding apparatus, the repetition is repetition of an identical data byte.
In accordance with a preferred embodiment of the encoding apparatus, the copying is copying of data of an immediately preceding line.
In accordance with a preferred embodiment of the encoding apparatus, the raw data is a direct designation of a data sequence of the given command code.
In accordance with a preferred embodiment of the encoding apparatus, the given command code is related to image data of two or more dimensions correlated in horizontal and vertical directions.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.